// https://leetcode.cn/problems/validate-stack-sequences/

// 算法思路总结：
// 1. 模拟栈的入栈出栈过程验证序列合法性
// 2. 按照压入序列顺序入栈
// 3. 每次入栈后循环检查栈顶是否匹配弹出序列
// 4. 最终通过弹出完成数量验证序列有效性
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <stack>
#include <algorithm>

class Solution 
{
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        int m = pushed.size();
        int finish = 0;

        stack<int> st;

        for (const int& num : pushed)
        {
            st.push(num);
            while (st.empty() == false && finish < m && st.top() == popped[finish])
            {
                finish++;
                st.pop();
            }
        }

        return finish == m;
    }
};

int main()
{
    vector<int> pushed1 = {1,2,3,4,5}, popped1 = {4,5,3,2,1};
    vector<int> pushed2 = {1,2,3,4,5}, popped2 = {4,3,5,1,2};

    Solution sol;

    cout << (sol.validateStackSequences(pushed1, popped1) == 1 ? "True" : "False") << endl;
    cout << (sol.validateStackSequences(pushed2, popped2) == 1 ? "True" : "False") << endl;

    return 0;
}